// https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/

// 算法思路总结：
// 1. 多源最短路径解决砍树问题（按树高顺序）
// 2. 收集所有树木位置，按树高升序排序
// 3. 依次计算从当前位置到下一棵树的最短路径（BFS）
// 4. 任意两棵树之间不可达则返回-1
// 5. 时间复杂度：O(k×m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>

class Solution 
{
public:
    typedef pair<int, int> PII;
    int m, n;

    int cutOffTree(vector<vector<int>>& forest) 
    {
        m = forest.size(), n = forest[0].size();
        vector<PII> trees;

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (forest[i][j] > 1)
                {
                    trees.push_back({i, j});
                }
            }
        }

        sort(trees.begin(), trees.end(), [&](const PII& p1, const PII& p2){
            return forest[p1.first][p1.second] < forest[p2.first][p2.second];
        });

        int ret = 0, bx = 0, by = 0;
        for (int i = 0 ; i < trees.size() ; i++)
        {
            auto [a, b] = trees[i];

            int step = bfs(forest, bx, by, a, b);
            if (step == -1) return -1;

            ret += step;
            bx = a, by = b;
        }

        return ret;
    }

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool vis[51][51];

    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
    {
        if (bx == ex && by == ey) return 0;
        memset(vis, 0, sizeof(vis));

        queue<PII> q;
        q.push({bx, by});
        vis[bx][by] = true;

        int ret = 0;
        while (!q.empty())
        {
            int sz = q.size();

            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();

                if (a == ex && b == ey)
                {
                    return ret;
                }

                for (int i = 0 ; i < 4 ; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x < m && y < n && x >= 0 && y >= 0 && vis[x][y] == false && forest[x][y] > 0)
                    {
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }

            ret++;
        }

        return -1;
    }
};

int main()
{
    vector<vector<int>> forest1 = {{1,2,3},{0,0,4},{7,6,5}};
    vector<vector<int>> forest2 = {{1,2,3},{0,0,0},{7,6,5}};

    Solution sol;

    cout << sol.cutOffTree(forest1) << endl;
    cout << sol.cutOffTree(forest2) << endl;

    return 0;
}